package com.example.leetcode.DFS;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 题目描述
 * 给定一个整数 n 和一个整数 k，求在 1 到 n 中选取 k 个数字的所有组合方法。
 * 输入输出样例
 * 输入是两个正整数 n 和 k，输出是一个二维数组，表示所有组合方式。
 * Input: n = 4, k = 2
 * Output: [[2,4], [3,4], [2,3], [1,2], [1,3], [1,4]]
 * 这里二维数组的每个维度都可以以任意顺序输出。
 *
 * @Description TODO
 * @date 2021/5/19 10:55
 * @Author liuzhihui
 * @Version 1.0
 */
public class Solution_5_77 {
    public static void main(String[] args) {
        int n = 4;
        int k =2;
        List<List<Integer>> combine = combine(n, k);

        for (List<Integer> list : combine) {
            for (Integer integer : list) {
                System.out.print(integer+" ");
            }
            System.out.println();
        }

    }
    // 回溯算法 + 剪枝
    public static List<List<Integer>> combine(int n, int k) {
        // 结果集
        List<List<Integer>> result = new ArrayList<>();
        // 记录一个组合
        List<Integer> temp = new ArrayList<>();
        int pos =1;
        dfs(n, k, result, temp, pos);
        return result;
    }
    private static void dfs(int n, int k, List<List<Integer>> result, List<Integer> temp,int pos) {
        // 递归出口，找到一个组合
        if (k == temp.size()){
            // 将组合添加到结果集中
            result.add(new ArrayList<>(temp));
            return;
        }
        // 遍历所有选择
        // 通过pos来剪枝
        // 如果 i 始终等于 1, 那么会出现[1,2],[2,1]这样的重复元素，而实际上只需要[1,2]即可
        // 设置i = pos，并且递归的时候传i,能起到剪枝的效果,剪掉的元素都是，[pos,pos]前的元素
        // 比如: [2,2]前的元素，[2,1]被剪枝；[3,3]前的元素被剪枝，即[3,1],[3,2]被剪枝
        // 但是剪枝[pos,pos]前的元素还是不够的，【pos,pos】本身还是要剪枝
        // 因此，递归的时候传，i+1，把【pos,pos】也给剪枝
        for (int i = pos; i <= n; i++) {
            // 将当前元素添加到组合中
            temp.add(i);
            // 继续寻找下一个元素
            dfs(n,k,result,temp,i + 1);
            // 回溯，寻找别的组合
            temp.remove(temp.size() -1);
        }
    }

}
//不剪枝
//1 1
//1 2
//1 3
//1 4
//2 1
//2 2
//2 3
//2 4
//3 1
//3 2
//3 3
//3 4
//4 1
//4 2
//4 3
//4 4
//第一次剪枝
//1 1
//1 2
//1 3
//1 4
//2 2
//2 3
//2 4
//3 3
//3 4
//4 4
//第二次剪枝
//1 2
//1 3
//1 4
//2 3
//2 4
//3 4